package com.felix.algorithms.planning;

/**
 * CutRope
 *
 * @author xuejinhua
 * @date 2018/9/11 10:49
 */
public class CutRope {

    public static int solution(int length) {
        if (length < 2) {
            return 0;
        }
        if (length == 2) {
            return 1;
        }
        if (length == 3) {
            return 2;
        }
        int[] array = new int[50];
        array[0] = 0;
        array[1] = 1;
        array[2] = 2;
        array[3] = 3;
        for (int i = 4; i < length + 1; i++) {
            int max = 0;
            for (int j = 1; j < i / 2 + 1; j++) {
                int temp = array[j] * array[i - j];
                max = temp > max ? temp : max;
            }
            array[i] = max;
        }
        return array[length];
    }

    public static void main(String[] args) {
        System.out.println(solution(9));
    }
}
